package interview;


public class lc33 {
    public static void main(String[] args) {
        System.out.println(search(new int[]{4,5,6,7,0,1,2}, 0));
        System.out.println(search2(new int[]{1,3}, 3));
        System.out.println(search(new int[]{1,2,3,4,5,6}, 4));
    }
    public static int search2(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        //利用二分法寻找旋转的节点旋转节点位于r处
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(nums[mid] > nums[r])
                l = mid + 1;
            else
                r = mid - 1;
        }
        // 如果目标小于最后一个，则对后半部分进行二分查找
        if(target <= nums[n - 1]){
            l = l;
            r = n;
        }
        // 否则，对前半部分二分查找
        else {
            l = 0;
            r = l;
        }
        while(l < r){
            int mid = l + (r - l) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] > target)
                r = mid;
            else
                l = mid + 1;

        }
        if(nums[l] == target)
            return l;
        return -1;
    }


    public static int search(int[] nums, int target) {
        int n = nums.length;
        if(n == 0)
            return -1;
        int l = 0, r = n - 1;
        //利用二分法寻找直接判断，类似于找旋转点
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(nums[mid] == target)
                return mid;
            //中间点位于前半部分
            if(nums[mid] > nums[r]){
                //判断目标值是否位于左端点与中间点之间
                if(nums[mid] > target && target >= nums[l])
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            //中间点位于后半部分
            else{
                //判断目标值是否位于中间点与右端点之间
                if(nums[mid] < target && target <= nums[r])
                    l = mid + 1;
                else
                    r = mid - 1;
            }

        }
        return -1;
    }
}
